// in calculating the distance between cluster center and data point, can actually use the divide and conquer
// algorithm used in calculating closest points
// may be add this in the next version

package roman.algorithm;

import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Random;
import java.util.Scanner;

public class Kmeans {
	Random rd = new Random(System.currentTimeMillis());
	int dataLength = 10000;
	int runs = 500;
	double[] x;
	double[] y;
	int k = 4;
	double[] centerX = new double[k];
	double[] centerY = new double[k];
	int[][] belongTo;
	double[] objectValues = new double[runs];
	int finalIndex=0;
	
	public void kmeans(int run){
		// find new cluster centers
		double[] dist = new double[k];
		double objectValue = 0;
		double prevValue = 0;
		boolean firstRun = true;
		double[] cumulativeX = new double[dataLength];
		double[] cumulativeY = new double[dataLength];
		int[] points = new int[k];
		
		while(true){
			for(int i = 0; i < dataLength; i++){
				cumulativeX[i]=0;
				cumulativeY[i]=0;
			}
			for(int i = 0; i<k; i++){
				points[i]=0;
			}
			for(int i=0;i<dataLength;i++){
				cumulativeX[belongTo[run][i]] += x[i];
				cumulativeY[belongTo[run][i]] += y[i];
				points[belongTo[run][i]]++;
			}
			for(int i=0;i<k;i++){
				centerX[i] = cumulativeX[i]/(double)points[i];
				centerY[i] = cumulativeY[i]/(double)points[i];
			}
			// calculate the object function value
			objectValue = 0;
			for(int i =0; i<dataLength; i++){
				for(int j = 0; j<k;j++){
					dist[j] = Math.sqrt((x[i]-centerX[j])*(x[i]-centerX[j])+(y[i]-centerY[j])*(y[i]-centerY[j]));
				}
				int index = 0;
				for(int j = 0; j<k; j++){
					if(dist[index]>dist[j]){
						index = j;
					}
				}
				objectValue += dist[index];
				belongTo[run][i]=index;
			}
//			System.out.println(Math.abs(objectValue-prevValue));
			if((Math.abs(objectValue-prevValue))<5 && firstRun == false){
				objectValues[run]=objectValue;
				break;
			}
			firstRun = false;
			prevValue = objectValue;
		}
		
	}
	public void process() throws IOException{
		Scanner sc = new Scanner(new FileInputStream("testdata\\data0"));
		x = new double[dataLength];
		y = new double[dataLength];
		belongTo = new int[runs][dataLength];
		int counter = 0;
		int tmp;
		double[] dist = new double[k];

		while(sc.hasNext()){
			x[counter] = sc.nextDouble();
			y[counter] = sc.nextDouble();
			counter++;
		}
		
		for(int run =0; run<runs; run++){
			for(int i=0; i<dataLength;i++){
				belongTo[run][i]=k+1;
			}
			for(int i =0; i<k; i++){
				tmp = rd.nextInt(dataLength);
				centerX[i] = x[tmp];
				centerY[i] = y[tmp];
			}
			
			// assign the points to a center
			int index;
			for(int i =0; i<dataLength; i++){
				for(int j = 0; j<k;j++){
					dist[j] = Math.sqrt((x[i]-centerX[j])*(x[i]-centerX[j])+(y[i]-centerY[j])*(y[i]-centerY[j]));
				}
				index = 0;
				for(int j = 0; j<k; j++){
					if(dist[index]>dist[j]){
						index = j;
					}
				}
				belongTo[run][i]=index;
			}
			kmeans(run);
		}
		finalIndex=0;
		for(int i =0; i < runs;i++){
			if(objectValues[finalIndex]>objectValues[i])
				finalIndex=i;
		}
		output();
	}
	
	public void output() throws IOException{
		PrintWriter pw1 = new PrintWriter( new BufferedWriter(new FileWriter("kmeans_1")));
		PrintWriter pw2 = new PrintWriter( new BufferedWriter(new FileWriter("kmeans_2")));
		PrintWriter pw3 = new PrintWriter( new BufferedWriter(new FileWriter("kmeans_3")));
		PrintWriter pw4 = new PrintWriter( new BufferedWriter(new FileWriter("kmeans_4")));
		for(int i=0; i<dataLength; i++){
			if(belongTo[finalIndex][i]==0){
				pw1.println("1"+" "+x[i]+" "+y[i]);
				continue;
			}
			if(belongTo[finalIndex][i]==1){
				pw2.println("2"+" "+x[i]+" "+y[i]);
				continue;
			}
			if(belongTo[finalIndex][i]==2){
				pw3.println("3"+" "+x[i]+" "+y[i]);
				continue;
			}
			if(belongTo[finalIndex][i]==3){
				pw4.println("4"+" "+x[i]+" "+y[i]);
				continue;
			}
		}
		pw1.flush();
		pw1.close();
		pw2.flush();
		pw2.close();
		pw3.flush();
		pw3.close();
		pw4.flush();
		pw4.close();
	}
	
	public static void main (String[] argv) throws IOException{
		Kmeans o = new Kmeans();
		o.process();
	}
}